package com.congee02;

import java.util.Arrays;

public class MinFallingPathSum_TL {

    public int minFallingPathSum(int[][] matrix) {

        for (int[] c : cache) {
            Arrays.fill(c, -1);
        }

        int ans = Integer.MAX_VALUE;
        for (int i = 0 ; i < matrix.length ; i ++ ) {
            ans = Math.min(ans, process(matrix, 0, i));
        }
        return ans;
    }

    private int[][] cache = new int[101][101];
    private int process(int[][] matrix, int row, int col) {
        if (row == matrix.length) {
            return 0;
        }
        if (col < 0 || col >= matrix.length) {
            return Integer.MAX_VALUE >>> 1;
        }
        if (cache[row][col] == -1) {
            cache[row][col] = matrix[row][col] + Math.min(
                    process(matrix, row + 1, col - 1),
                    Math.min(
                            process(matrix, row + 1, col),
                            process(matrix, row + 1, col + 1)
                    )
            );
        }
        return cache[row][col];
    }

}
